Modern Coin-Weighing Puzzles
I usually give a lot of lectures and I never used to announce them in my blog. This time I will give a very accessible lecture at the MIT “Women in Mathematics” series. It will be on Wednesday October 6th at 5:30-6:30 PM in room 2-135. If you are in Boston, feel free to join. Here is the abstract.
I will discuss several coin-weighing puzzles and related research. Here are two examples of such puzzles:
1. Among 10 given coins, some may be real and some may be fake. All real coins weigh the same. All fake coins weigh the same, but have a different weight than real coins. Can you prove or disprove that all ten coins weigh the same in three weighings on a balance scale?
2. Among 100 given coins, four are fake. All real coins weigh the same. All fake coins weigh the same, but they are lighter than real coins. Can you find at least one real coin in two weighings on a balance scale?
You are not expected to come to my talk with the solutions to the above puzzles, but you are expected to know how to find the only fake coin among many real coins in the minimum number of weighings.
Share:
Anonymous Rex:
Regarding the last sentence, do you mean one fake coin that you know weighs less, or one fake coin that may weigh less or may weigh more?
I think the latter is actually a bit much to ask from people.
5 October 2010, 12:06 pmTanya Khovanova:
Rex,
Oops, I meant the classical question where you know that fake coins weigh less.
5 October 2010, 12:13 pmQuick Links | A Blog Around The Clock:
[…] Modern Coin-Weighing Puzzles […]
6 October 2010, 11:54 pmsaar:
sorry, english is not my language
the second problem, 100 coins is the same as 50 or 1000 0r 13.
divide to three parts, n,n, m
such that 2n>m>n
weight n aginst n. if there is one side heavier divude to 2, all coins in heavy side now are real.
else weight m against n and (m-n)coins from second n.
please tell me the first solution
20 October 2010, 10:51 amdebanshu:
I think the solution for the first one goes like this :
First we divide the 10 coins into 5 and 5.
Weigh them.If do not balance we are done.
If not we remove one coin(*) from one of the piles of 5.
And divide it into 2 and 2.
Weigh them.If they do not balance we are done.
If not we remove one coin from one of the piles of 2.
And weigh it with the coin(*) removed before the weighing.
If they balance we can be sure all of them are either real ones or fake ones.
If they do not the conclusion is one must be real and another fake.
**note: when pan balances with equal no. of coins it means there are exactly same no. of
25 October 2010, 11:14 amfake and real coins on both sides.But when it does not it means they are unequal no. of real
and as well as fake coins on both the pans.
saar:
sorry, it is not a solution/
26 October 2010, 5:27 amin the second time, there may be in each sidr one real coin and oae fake/
the thurd time we do not know uf noth sides are real or fake.
debanshu:
Thanks saar yes I see your point.
Actually in this problem there are 3 cases :
1) 10 either real or fake.
2) 4 real and 6 fake or 6 real and 4 fake.
3) 2 real and 8 fake or 2 fake and 8 real.
In fact there are 6 cases but symmetric cases can be handled by the same solution.
The procedure I gave works for 1) and 2).
But fails for 3) in which case whatever you said can arise as a possibility.
Thanks again. You can try to mend the proof 🙂
27 October 2010, 4:30 amdebanshu:
Sorry once again …
My soln does not cover 2) , but works for 1) and 3).
27 October 2010, 4:31 amReila:
I think I got the first one. I like reasoning these out against the temptation to check the comments section by I came to a similar conclusion. The first weighing should be 5:5, that way we rule out any possibility but a distribution of 4:6, 2:8, or 0:10. Any time the weighings are not equal the solution is trivial, so I will assume that all weighings are balanced. I will only consider it from the perspective of the minority group which I arbitrarily call as “fake coins” (it’s equivalent if you consider it from the perspective of real coins).
Number the coins from 1 to 10 and the weighings are as follows:
1,2,3,4,5 : 6,7,8,9,10
If they balance, then we expect that there is either 2, 1, or 0 fake coins on each side.
1,2,6 : 3,4,5
If they balance, it means that either there is either 1 or 0 fake coins in 1,2. There is either 1 or 0 fake coins in 3,4,5.
3,4,5,6 : 7,8,9,10
Assume 6 to be a fake coin. There must be a fake coin in 7,8,9,10 to balance it. But according to the previous weighing there must be at least one fake coin in 3,4,5 to balance the 6 on the left side. So there must be at least two fake coins in 7,8,9,10 to balance the two fake coins on the left side, which makes at least 3 fakes in 6,7,8,9,10. This is inconsistent with the original statement that the number of fake coins must be at most 2 in 6,7,8,9,10. Therefore 6 cannot be a fake coin. (Note, I’m using the term fake coin as the coin in minority.)
Now that we know 6 is a real coin, we know that there is 0 or 1 fake coins in 3,4,5 and 0 or 1 fake coins in 7,8,9,10. Therefore according to the first weighing, 1,2 must be real coins. According to the second weighing, 3,4,5 must also be all real coins. And now we realize by the third weighing that 7,8,9,10 must also be real coins.
Therefore the only way all three of these weighings would balance is if all of the coins were of the same weight.
12 April 2013, 4:54 am